package com.bluebridgecup.BasicAlgorithms.BinarySearch;

import java.util.Scanner;

public class ChocolateCutting {
    static int n, k;
    static int[] h, w;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 巧克力的数量
        n = in.nextInt();
        // 需要切割得到的最少巧克力块数 k
        k = in.nextInt();
        // 高度数组h
        h = new int[n + 5];
        // 宽度数组w
        w = new int[n + 5];
        // 读取每块巧克力的高度和宽度
        for (int i = 1; i <= n; i++) {
            // 读取第i块巧克力的高的
            h[i] = in.nextInt();
            // 读取第i块巧克力的宽度
            w[i] = in.nextInt();
        }

        int l = 1;
        int r = 100000;

        // 二分查找过程中，当左边界小于右边界时继续查找
        while (l < r) {
            // 计算中间值
            int mid = r + l + 1 >> 1;
            // 调用check方法检查以mid为边长切割巧克力能否得到不少于k块
            if (check(mid)) {
                // 可以，则说明mid是一个可能的答案，更新左边界
                l = mid;
            } else {
                // 如果不可以，说明mid太大了，更新右边界为mid-1
                r = mid - 1;

            }
        }
        System.out.print(r);
        in.close();
    }

    // 检查以mid为边长切割巧克力能否得到不少于k块的方法
    static boolean check(int mid) {
        // 用于记录切割后得到的巧克力总块数，使用long避免整数越界
        long ans = 0;
        //遍历每一块巧克力
        for (int i = 1; i <= n; i++) {
            //计算第i块巧克力以边长为mid切割后得到的块数，并累加
            ans += (h[i] / mid) * (w[i] / mid);
            // 如果累加的块数已经达到或超过k，说明满足条件，返回true
            if (ans >= k) {
                return true;
            }
        }
        // 遍历完所有巧克力后，块数仍然小于k，则返回false
        return false;
    }
}
